\documentclass[a4paper]{article}
\usepackage{geometry}
\usepackage{bm}
\usepackage{multicol}
\title{HOMEWORK02}
\author{3190101820 Weizhen Li}
\date{2021-10-28}
\geometry{left=1.2cm,right=1cm,top=2.5cm,bottom=2.5cm}
\begin{document}
\maketitle
\columnseprule=0.5pt
\begin{multicols}{2}
\section*{Theoretical problems}
\paragraph{\uppercase\expandafter\romannumeral1}
Since $f(x)=\frac{1}{x},x_{0}=1,x_{1}=2$, it's easy to get $p_{1}(f;x)$ by linear interpolation, namely,
\[p_{1}(f;x)=-\frac{1}{2}x+\frac{3}{2}\]
from the equations
\[f(x)-p_{1}(f;x)=\frac{f''(\xi(x))}{2}(x-x_{0})(x-x_{1})\]
and
\[\frac{1}{x}+\frac{1}{2}x-\frac{3}{2}=\frac{1}{2x}(x-1)(x-2)\]
we have $\xi(x)=\sqrt[3]{2x}$;\\
For $x\in[x_{0},x_{1}]$, max$\xi(x)=\xi(x_{1})=\sqrt[3]{4}$, min$\xi(x)=\xi(x_{0})=\sqrt[3]{2}$, and max$f''(\xi(x))=1$
\paragraph{\uppercase\expandafter\romannumeral2}
For general situation, from Lagrange formula, we have
\[p_{n}(x)=\sum_{k=0}^{n}f_{k}l_{k}(x), l_{k}(x)=\prod_{i=0,i\ne k}^{n}\frac{x-x_{i}}{x_{k}-x_{i}}\]
In order to let $p \in \mathbb{P}_{2n}^{+}$, we can take
\[p_{n}(x)=\sum_{k=0}^{n}f_{k}\prod_{i=0,i\ne k}^{n}(\frac{x-x_{i}}{x_{k}-x_{i}})^{2}\].
\paragraph{\uppercase\expandafter\romannumeral3}
(1)For $n=1$, it holds because of
\[f[t,t+1]=\frac{f(t+1)-f(t)}{t+1-t}=\frac{(e-1)^{1}}{1!}e^{t}\]
Suppose it still holds for $n=2,3,...,k$, then when $n=k+1$, we have
\[f[t,..,t+k+1]=\frac{f[t+1,...,t+k+1]-f[t,...,t+k]}{t+k+1 - t}\]
\[=\frac{\frac{(e-1)^{k}}{k!}e^{t+1}-\frac{(e-1)^{k}}{k!}e^{t}}{k+1}=\frac{(e-1)^{k+1}}{(k+1)!}e^{t}\]
Hence it holds for $n=k+1$; By induction, the proof is completed.\\
(2)From (1), we get
\[f[0,1,...,n]=\frac{(e-1)^{n}}{n!}=\frac{1}{n!}f^{(n)}(\xi)=\frac{e^{\xi}}{n!}\]
So $\xi=n\ln(e-1)$, since $\ln(e-1) > \frac{1}{2}$, $\xi$ is located to the right of the midpoint $\frac{n}{2}$. 
\paragraph{\uppercase\expandafter\romannumeral4}
(1)From $f(0)=5,f(1)=3,f(3)=5,f(4)=12$, yields\\
$f[x_{0}]=5, f[x_{0},x_{1}]=\frac{3-5}{1-0}=-2,\\ f[x_{1},x_{2}]=\frac{5-3}{3-1}=1, f[x_{2},x_{3}]=\frac{12-5}{4-3}=7\\
f[x_{0},x_{1},x_{2}]=\frac{1-(-2)}{3-0}=1, f[x_{1},x_{2},x_{3}]=\frac{7-1}{4-1}=2\\
f[x_{0},x_{1},x_{2},x_{3}]=\frac{2-1}{4-0}=\frac{1}{4}$ \\
By Newton formula, we have
\[p_{3}(f;x)=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)\]
\[=\frac{1}{4}x^{3}-\frac{9}{4}x+5\]
(2)We just use $x_{min}$ of $p_{3}(f;x)$ to estimate $x_{min}$ of $f$ in $(1,3)$.\\
Since $p'(x)=\frac{3}{4}(x^{2}-3)$, $x_{min}$ of $p$ is $\sqrt{3}$, which is the approximate value of the location $x_{min}$ of the minimum.
\paragraph{\uppercase\expandafter\romannumeral5}
(1)Because of the definition $f[x_{0},x_{0},...,x_{0}]=\frac{f^{(n)}(x_{0})}{n!}$, we have\\
$f[1,1]=\frac{f'(1)}{1!}=7, f[2,2]=\frac{f'(2)}{1!}=448, f[1,1,1]=\frac{f''(1)}{2!}=21$, and 
$f[0,1]=1, f[1,2]=127$\\
By Theorem 3.17, yields
\[f[0,1,1,1,2,2]=\frac{1}{4}f[0,1]+f[1,1]-\frac{7}{4}f[1,2]+\frac{1}{2}f[2,2]\]
\[+f[1,1,1]=30\]
(2)$f^{(5)}(x)=\frac{7!}{2}x^{2}$, with $\frac{f^{(5)}(\xi)}{5!}=30$,yields $\xi=\sqrt{\frac{10}{7}}$.
\paragraph{\uppercase\expandafter\romannumeral6}
(1)We can obtain a polynomial of degree $\le$ 4 by Hermite interpolation.Suppose
\[p(x)=\varphi_{1}(x)+2\varphi_{2}(x)-\varphi_{3}(x)\]
where $\varphi_{1},\varphi_{2},\varphi_{3}$ satisfy\\
$\varphi_{1}(0)=1,\varphi_{1}(1)=\varphi_{1}(3)=0,\varphi_{1}'(1)=\varphi_{1}'(3)=0$\\
$\varphi_{2}(1)=1,\varphi_{2}(0)=\varphi_{2}(3)=0,\varphi_{2}'(1)=\varphi_{2}'(3)=0$\\
$\varphi_{3}(0)=\varphi_{3}(1)=\varphi_{3}(3)=0,\varphi_{3}'(1)=1,\varphi_{3}'(3)=0$\\
respectively.\\
Here we only show how to get $\varphi_{1}$,and the other two are similar.We know $\varphi_{1}$ has two roots of multiplicity 2.
So it has factors $(x-1)^{2}$ and $(x-3)^{2}$;In addition,$\varphi_{1}(0)=1$ and degree $\le$ 4, yields
\[\varphi_{1}(x)=\frac{1}{9}(x-1)^{2}(x-3)^{2}\]
Similarly,
\[\varphi_{2}(x)=\frac{1}{4}x(x-3)^{2},\varphi_{3}(x)=\frac{1}{4}x(x-1)(x-3)^{2}\]
Then we have $p(2)=\frac{11}{18}$,which is the estimation of $f(2)$. \\
(2)With $f\in \mathbb{C}^{5}[0,3]$ and $|f^{(5)}(x)| \le$ M, by Theorem 3.33, derive the maximum possible error:
\[\frac{M}{5!}(2-0)^{1}(2-1)^{2}(2-3)^{2}=\frac{M}{60}\].
\paragraph{\uppercase\expandafter\romannumeral7}
We just prove it by induction.And we just prove the first equation which is about forward difference,since the second is similar.
For $k=1$,it holds because of
\[\bigtriangleup f(x)=1!h\frac{f(x+h)-f(x)}{h}=1!hf[x_{0},x_{1}]\]
Suppose it still holds for $k=2,3...n$,then when $k=n+1$,we have
\[\bigtriangleup^{n+1} f(x)=\bigtriangleup\bigtriangleup^{n}f(x)=\bigtriangleup^{n}f(x+h)-\bigtriangleup^{n}f(x)\]
\[=n!h^{n}f[x_{1},x_{2},...,x_{n+1}]-n!h^{n}f[x_{0},x_{1},...,x_{n}]\]
\[=(n+1)!h^{n+1}\frac{f[x_{1},x_{2},...,x_{n+1}]-f[x_{0},x_{1},...,x_{n}]}{x_{n+1}-x_{0}}\]
\[=(n+1)!h^{n+1}f[x_{0},x_{1},...,x_{n+1}]\]
Hence it holds for $k=n+1$.By induction,proof is completed.Similarly,the second equation also holds.
\paragraph{\uppercase\expandafter\romannumeral8}
Prove it by induction.For $n=1$,it holds because of
\[\frac{\partial}{\partial x_{0}}f[x_{0},x_{1}]=\frac{\partial}{\partial x_{0}}\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}\]
\[=\frac{f][x_{0},x_{1}]-f[x_{0},x_{0}]}{x_{1}-x_{0}}=f[x_{0},x_{0},x_{1}]\]
Suppose it holds for $n=2,3,...,k$,then when $n=k+1$,we have
\[\frac{\partial}{\partial x_{0}}f[x_{0},x_{1},...,x_{k+1}]=\frac{\partial}{\partial x_{0}}\frac{f[x_{1},...,x_{k+1}]-f[x_{0},...,x_{k}]}{x_{k+1}-x_{0}}\]
\[=\frac{f[x_{1},...,x_{k+1}]-f[x_{0},...,x_{k}]-f[x_{0},x_{0},...,x_{k}](x_{k+1}-x_{0})}{(x_{k+1}-x_{0})^{2}}\]
\[=\frac{f[x_{0},x_{1},...,x_{k+1}]-f[x_{0},x_{0},...,x_{k}]}{x_{k+1}-x_{0}}=f[x_{0},x_{0},x_{1},...,x_{k+1}]\]
Hence it still holds for $n=k+1$.By induction,proof is complete.Similarly,for another variable $x_{i}$,
\[\frac{\partial}{\partial x_{i}}f[x_{0},x_{1},...,x_{n}]=f[x_{0},x_{1},..,x_{i},x_{i},..,x_{n}]\]
\paragraph{\uppercase\expandafter\romannumeral9}
Taking $x'=\frac{2x-a-b}{b-a}$,then for $x\in[a,b], x'\in[-1,1]$.And we have
\[max\limits_{x\in[a,b]}|a_{0}x^{n}+a_{1}x^{n-1}...+a_{n}|\]
\[=max\limits_{x'\in[-1,1]}|c_{0}(x')^{n}+c_{1}(x')^{n-1}+...+c_{n}|\]
where $c_{i}\in \mathbb{R}$ and $c_{0}=\frac{a_{0}(b-a)^{n}}{2^{n}}\ne0$.By Corollary 3.41,yields
\[max\limits_{x'\in[-1,1]}|c_{0}(x')^{n}+c_{1}(x')^{n-1}+...+c_{n}| \ge \frac{|c_{0}|}{2^{n-1}}\]
Meanwhile,when $|c_{0}(x')^{n}+c_{1}(x')^{n-1}+...+c_{n}|=|\frac{c_{0}T_{n}(x')}{2^{n-1}}|,$ the equality holds.Hence
\[min\; max\limits_{x\in[a,b]}|a_{0}x^{n}+a_{1}x^{n-1}+...+a_{n}|\]
\[=\frac{|c_{0}|}{2^{n-1}}=\frac{|a_{0}|(b-a)^{n}}{2^{2n-1}}}\]
\paragraph{\uppercase\expandafter\romannumeral10}
Suppose it does not hold.Namely,\\
\[\exists p\in\mathbb{P}_{n}^{a},s.t. \parallel p\parallel_{\infty} < \parallel \hat{p}_{n}(x)\parallel_{\infty}=\frac{1}{|T_{n}(a)|}\]
Firstly,we prove $T_{n}(a)(a>1)$ is positive by an easy induction.From the definition,we have
\[T_{0}(x)=1, T_{1}(x)=x,...,T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x)\]
Obviously $T_{1}(a)>T_{0}(a)>0$,suppose it holds until $k=n$ i.e. $T_{k}(a)>T_{k-1}(a)$ for $k=2,3,...,n$.Then 
when $k=n+1$,we have 
\[T_{n+1}(a)-T_{n}(a)=(2a-1)T_{n}(a)-T_{n-1}(a)>0\]
Hence it holds that $T_{n}(a)>0$ for $n=0,1,2.....$\\
Consider the polynomial $Q(x)=\frac{T_{n}(x)}{T_{n}(a)}-p(x).$
\\Obviously we have $Q(a)=0$.
By Theorem 3.38, $T_{n}(x)$ has its extrema $n+1$ times at the point $x'_{k}$ defined in (3.42).Hence $Q(x)$ has alternating signs at these $n+1$ points,
i.e. $Q(x)$ must has $n$ zeros in $[-1,1]$.Since $Q(a)=0$ and $a>1$,$Q(x)$ has $n+1$ zeros.However,by the construction of $Q(x)$,the degree of it is at most $n$.
Therefore,$Q(x)\equiv0$ i.e. $p(x)=\frac{T_{n}(x)}{T_{n}(a)}$.Its maximum is equal to $\frac{1}{T_{n}(a)}$.This is a contradiction to the hypothesis.
That is,
\[\forall p\in\mathbb{P}_{n}^{a}, \parallel \hat{p}_{n}(x)\parallel_{\infty} \le \parallel p\parallel_{\infty}\]

\end{multicols}
\end{document}